package com.liunian.algorithmstudy.monotonicstack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class DailyTemperatures739 {

	/**
	 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，
	 下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

	 示例 1:
	 输入: temperatures = [73,74,75,71,69,72,76,73]
	 输出: [1,1,4,2,1,1,0,0]

	 示例 2:
	 输入: temperatures = [30,40,50,60]
	 输出: [1,1,1,0]

	 示例 3:
	 输入: temperatures = [30,60,90]
	 输出: [1,1,0]
	 */
	public int[] dailyTemperatures(int[] temperatures) {
		Deque<Integer> deque = new LinkedList<>();
		deque.addFirst(0);
		int[] res = new int[temperatures.length];
		for (int i = 1; i < temperatures.length; i++) {
			Integer peeked = deque.peekFirst();
			if (temperatures[i] > temperatures[peeked]) {
				while (!deque.isEmpty() && temperatures[deque.peekFirst()] < temperatures[i]) {
					Integer polled = deque.pollFirst();
					res[polled] = i - polled;
				}
			}
			deque.push(i);
		}
		return res;
	}

	public static void main(String[] args) {
		DailyTemperatures739 temperatures739 = new DailyTemperatures739();
		System.out.println(Arrays.toString(temperatures739.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
	}

}
